//
//  main.c
//  C_Study
//
//  Created by rui on 12-8-31.
//  Copyright (c) 2012年 Wang Rui. All rights reserved.
//



/*
 *排序
 */

#include "types.h"


void printArray(int *arr,int length){
	for (int i=0; i<length; i++) {
		printf("%d ",arr[i]);
	}
	printf("\n");
}


/*
 *直接插入排序 o(n2) 稳定
 */

void insert_sort(int *arr,int length){
	
	for (int i=1; i<length; i++) {
		if (arr[i] < arr[i-1]) {//小于时是代表i个是无序的
			int t = arr[i];
			int j;
			
			for (j = i-1; t<arr[j] && j>=0; j--) {//每次只要小于一个数，就将次数向后移动一位
				arr[j+1] = arr[j];
			}

			arr[j+1] = t;//插入合适位置
		}
	}
	
}


/*
 *折半插入排序
 */

void BIInsertSort(int *arr,int length){
	for (int i = 1; i<length; i++) {
		if (arr[i] < arr[i-1]) {//有序不再移动
			
			int t = arr[i];
			int low = 0; 
			int high = i-1; 
			int mid,j;
			
			while (low<=high) {//寻找插入位置:(high+1)
				mid = (low+high)/2;
				if (t < arr[mid]) {
					high = mid-1;
				}
				else {
					low = mid+1;
				}
			}
			
			for (j=i-1; j>=high+1; j--) {
				arr[j+1] = arr[j];
			}
			
			arr[j+1] = t;
		}
	}
}

/*
 *冒泡排序 o(n2) 稳定
 */
void bubble_sort(int *arr,int length){
	for (int i=1; i<length; i++) {
		for (int j=0; j<length-i; j++) {
			if (arr[j]>arr[j+1]) {
				int t = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = t;
			}
		}
	}
}


/*
 *简单选择排序 o(n2) 不稳定
 */

void SelectSort(int *arr,int length){
	for (int i=0; i<length; i++) {
		int min = i;
		for (int j=i+1; j<length; j++) {
			if (arr[j]<arr[min]) {
				min = j;
			}
		}
		
		int t = arr[i];
		arr[i] = arr[min];
		arr[min] = t;
	}
}


/*
 *堆排序 o[nlogn] 其思想就是通过一轮堆筛选，选出最大的放在树顶，然后和数组最后一个交换。 依此类推
 */

/* 已知H[s..m]中记录的关键字除H[s]之外均满足堆的定义，本函数调整H[s]的关键字,使H[s..m]成为一个大顶堆*/ 
void HeapAdjust(int *H,int s,int m)//s为下界，m为上界
{   
	int rc;
	int j;
	rc=H[s];
	
	for(j=2*s+1;j<=m;j=j*2+1)/* 沿key较大的孩子结点向下筛选 */
	{ 
		if(j<m && H[j]<H[j+1])//比较左子节点和右子节点的大小
			++j; /* j为key较大的记录的下标 */
		
		if(rc >= H[j])
			break; /* rc应插入在位置s上 */
		
		H[s]=H[j];
		s=j;
	}
	H[s]=rc; /* 插入 */
}

void HeapSort(int *H,int length)
{
	int maxSubscript = length-1; //最后一个下标
	
	for(int i=(maxSubscript-1)/2;i>=0;--i)//下标为i的节点，父节点下标为(i-1)/2
	{/*把H[0..length-1]建成大顶堆 */
		HeapAdjust(H,i,maxSubscript);
	}
	
	for(int j=maxSubscript;j>0;--j)
	{ /* 将堆顶记录和当前未经排序子序列H[0..i]中最后一个记录相互交换 */
		int t=H[0];
		H[0]=H[j];
		H[j]=t;
		HeapAdjust(H,0,j-1); /* 将H[0..i-1]重新调整为大顶堆 */
	}
}



/*
 *归并排序 o(nlogn) 稳定
 */
void Merge(int SR[],int TR[],int i,int m,int n)/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]*/
{ 
	int j,k,l;
	for(j=m+1,k=i; i<=m&&j<=n; ++k)//k用于标记归并数组的下标
	{/* 将SR中记录由小到大地并入TR */
		if (SR[i] <= SR[j])
			TR[k]=SR[i++];
		else
			TR[k]=SR[j++];
	}
	/*以下两个if表示有一边已经全部归并好，而此时循环已结束，所以要补齐另一边*/
	if(i<=m)
		for(l=0;l<=m-i;l++)
			TR[k+l]=SR[i+l]; /* 将剩余的SR[i..m]复制到TR */
	if(j<=n)
		for(l=0;l<=n-j;l++)
			TR[k+l]=SR[j+l]; /* 将剩余的SR[j..n]复制到TR */
}

void MSort(int SR[],int TR[],int s, int t)/*将SR[s..t]归并排序为TR1[s..t],s为下界，t为上界*/
{ 
#define MAXSIZE 20
	int SR2[MAXSIZE]; //申请空间来存放归并好的序列，SR2[]保存的是两个子序列归并后的结果
	
	if(s==t)
		TR[s]=SR[s];//此时为单个有序
	else
	{
		int m=(s+t)/2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
		MSort(SR,SR2,s,m); /* 递归地将SR[s..m]归并为有序的SR2[s..m] */
		MSort(SR,SR2,m+1,t); /* 递归地将SR[m+1..t]归并为有序的SR2[m+1..t] */
		Merge(SR2,TR,s,m,t); /* 将SR2[s..m]和SR2[m+1..t]归并到TR1[s..t] */
	}
}

void MergeSort(int *arr,int length)
{ 
	MSort(arr,arr,0,length-1);
}


/*
 *快速排序 o(nlogn) 不稳定
 */


/* 交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位,并返回其所在位置，此时在它之前(后)的记录均不大(小)于它.*/
int Partition(int *arr,int low,int high)
{ 
	int t;
	int pivotkey = arr[low];/* 用子表的第一个记录作枢轴记录 */
	
	while(low<high)/* 从表的两端交替地向中间扫描 */
	{ 
		while(low<high && arr[high]>=pivotkey)
			--high;
		t=arr[low]; /* 将比枢轴记录小的记录交换到低端 */
		arr[low]=arr[high];
		arr[high]=t;
		
		while(low<high && arr[low]<=pivotkey)
			++low;
		t=arr[low]; /* 将比枢轴记录大的记录交换到高端 */
		arr[low]=arr[high];
		arr[high]=t;
	}
	return low; /* 返回枢轴所在位置 */
}

void QSort(int *arr,int low,int high)
{
	if(low<high)
	{ /* 长度大于1 */
		int pivotloc=Partition(arr,low,high); /* 将L.r[low..high]一分为二 */
		QSort(arr,low,pivotloc-1); /* 对低子表递归排序，pivotloc是枢轴位置 */
		QSort(arr,pivotloc+1,high); /* 对高子表递归排序 */
	}
}

void QickSort(int *arr,int length)
{
	QSort(arr, 0, length-1);
}



/**********************************/
/* @main函数                       */
/**********************************/
int main(int argc, const char * argv[])
{
	int a[6] = {52,23,80,36,92,35};
	QickSort(a, 6);
	printArray(a, 6);
	
	return 0;
}

